package model_Ke;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import lib.Util;

public class UndirectedGraph extends IGraph {

	public UndirectedGraph(int[][] matrix, List<Point> numberPoints) {
		super(matrix, numberPoints);

	}

	public UndirectedGraph() {
	}

	public UndirectedGraph(MatrixWeight matrixWeight, List<Point> numberPoints) {
		super(matrixWeight, numberPoints);

	}

	private void formatData() {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				matrix[i][j] = 0;
			}
		}
	}

	@Override
	public boolean addPoint(Point point) {
		for (int i = 0; i < numberPoints.size(); i++) {
			if (numberPoints.get(i).equals(point)) {
				return false;
			}
		}
		numberPoints.add(point);
		setSizeAddPoint();
		return true;
	}

	@Override
	public boolean addPoint(String name) {
		for (int i = 0; i < numberPoints.size(); i++) {
			if (numberPoints.get(i).equals(name)) {
				return false;
			}
		}
		Point point = new Point(name);
		numberPoints.add(point);
		setSizeAddPoint();
		return true;

	}

	@Override
	public void removePoint(Point point) {
		for (int i = 0; i < numberPoints.size(); i++) {
			if (point.equals(numberPoints.get(i))) {
				numberPoints.remove(i);
				setSizeRemovePoint(i);
			}
		}

	}

	@Override
	public void removePoint(String name) {
		for (int i = 0; i < numberPoints.size(); i++) {
			if (numberPoints.get(i).equals(name)) {
				numberPoints.remove(i);
				setSizeRemovePoint(i);
			}
		}

	}

	@Override
	public void addEdge(Point start, Point end) {
		int col = 0;
		int row = 0;
		for (int i = 0; i < numberPoints.size(); i++) {
			if (numberPoints.get(i).equals(start))
				col = i;
			if (numberPoints.get(i).equals(end))
				row = i;
		}
		matrix[row][col] = 1;
		matrix[col][row] = 1;
	}

	@Override
	public void addEdge(String start, String end) {
		int col = 0;
		int row = 0;
		for (int i = 0; i < numberPoints.size(); i++) {
			// System.out.println(i);
			if (numberPoints.get(i).equals(start))
				row = i;
			if (numberPoints.get(i).equals(end))
				col = i;
		}
		// System.out.println(row + " " + col);
		matrix[row][col] = 1;
		matrix[col][row] = 1;
	}

	@Override
	public void removeEdge(Point start, Point end) {
		removeEdge(start.getName(), end.getName());

	}

	@Override
	public void removeEdge(String start, String end) {
		int row = 0;
		int col = 0;
		for (int i = 0; i < numberPoints.size(); i++) {
			if (numberPoints.get(i).equals(start))
				row = i;
			if (numberPoints.get(i).equals(end))
				col = i;
		}
		System.out.println(row + " " + col);
		matrix[row][col] = 0;
		matrix[col][row] = 0;

	}

	@Override
	public int[][] getMatrix() {
		// TODO Auto-generated method stub
		return null;
	}

	public MatrixWeight getMatrixWeight() {
		// TODO Auto-generated method stub
		return this.matrixWeight;
	}

	@Override
	public int getNumberPoints() {
		return 0;
	}

	public void setSizeAddPoint() {
		int matrix_new[][] = new int[matrix.length + 1][matrix.length + 1];
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				matrix_new[i][j] = matrix[i][j];
			}
		}
		for (int i = 0; i < matrix_new.length; i++) {
			matrix_new[i][matrix_new.length - 1] = 0;
			matrix_new[matrix_new.length - 1][i] = 0;
		}
		matrix = matrix_new;
	}

	public void setSizeRemovePoint(int point) {
		int matrix_new[][] = new int[matrix.length - 1][matrix.length - 1];
		boolean row = false, col = false;
		a: for (int i = 0; i < matrix.length; i++) {
			if (i == point) {
				row = true;
				continue a;
			}
			for (int j = 0; j < matrix.length; j++) {
				if (j == point) {
					col = true;
					continue;
				}

				if (row == true)
					matrix_new[i - 1][j] = matrix[i][j];

				else
					matrix_new[i - 1][j] = matrix[i][j];
			}
		}
		matrix = matrix_new;
	}

	@Override
	public String toString() {
		String temp = "\n ";
		for (int i = 0; i < numberPoints.size(); i++) {
			temp = temp + " " + numberPoints.get(i);
		}
		for (int i = 0; i < matrix.length; i++) {
			temp = temp + "\n" + numberPoints.get(i);
			for (int j = 0; j < matrix.length; j++) {
				temp = temp + " " + matrix[i][j];
			}
		}
		// System.out.println(temp + "\n");
		return temp + "\n";
	}

	@Override
	public int deg(String u) {
		int result = 0;
		for (int i = 0; i < this.size(); i++) {
			if (numberPoints.get(i).equals(u)) {
				for (int j = 0; j < this.size(); j++) {
					if (this.matrix[i][j] == 1) {
						result++;
					}

				}
				break;
			}
		}
		return result;
	}

	public int deg(int point) {
		int result = 0;
		for (int i = 0; i < this.size(); i++) {
			if (this.matrix[i][point] == 1) {
				result++;
			}
		}
		return result;
	}

	@Override
	public int numberSumEdge() {
		int result = 0;
		for (int i = 0; i < matrix.length; i++) {
			result += deg(this.numberPoints.get(i).getName());
		}
		return result / 2;
	}

	@Override
	public boolean isBipartite() {
		int colour[] = new int[this.size()];
		colour[0] = 1;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				if (matrix[i][j] == 1) {
					if (colour[j] == 0) {
						if (colour[i] == 1) {
							colour[j] = 2;
						} else {
							colour[j] = 1;
						}
					} else {
						if (colour[j] != 0 && (colour[j] == colour[i]))
							return false;
					}
				}
			}
		}
		for (int i = 0; i < colour.length; i++) {
			if (colour[i] == 0) {
				return false;
			}
		}
		return true;
	}

	@Override
	public boolean isConnection() {
		Stack<Integer> stack = new Stack<>();
		boolean visited[] = new boolean[this.size()];
		int v = 0;
		boolean cont = true;
		a: while (cont) {
			visited[v] = true;
			for (int i = 0; i < this.size(); i++) {
				if (matrix[v][i] == 1 && visited[i] == false) {
					stack.push(v);
					v = i;
					continue a;
				}
			}
			if (stack.size() != 0)
				v = stack.pop();
			else
				cont = false;
		}
		for (int i = 0; i < visited.length; i++) {
			if (visited[i] == false) {
				return false;
			}
		}
		return true;
	}

	@Override
	public int countNumberConnection() {
		Stack<Integer> stack = new Stack<>();
		boolean visited[] = new boolean[this.size()];
		int v = 0;
		boolean cont = true;
		int count = 1;
		a: while (cont) {
			visited[v] = true;
			for (int i = 0; i < this.size(); i++) {
				if (matrix[v][i] == 1 && visited[i] == false) {
					stack.push(v);
					v = i;
					continue a;
				}
			}
			if (stack.size() != 0)
				v = stack.pop();
			else {
				for (int i = 0; i < visited.length; i++) {
					if (visited[i] == false) {
						count++;
						v = i;
						continue a;
					}
				}
				cont = false;
			}
		}

		return count;
	}

	@Override
	public boolean hasWay(String start, String end) {
		Stack<Integer> stack = new Stack<>();
		int s = 0, e = 0;
		for (int i = 0; i < this.size(); i++) {
			if (numberPoints.get(i).equals(start))
				s = i;
			if (numberPoints.get(i).equals(end))
				e = i;
		}
		int v = s;
		boolean cont = true;
		int m[][] = matrix;
		a: while (cont) {
			for (int i = 0; i < this.size(); i++) {
				if (m[v][i] == 1) {
					if (i == e)
						return true;
					else {
						stack.push(v);
						m[v][i] = 0;
						v = i;
						continue a;
					}
				}
			}
			if (stack.size() != 0) {
				v = stack.pop();
				continue a;
			} else {
				cont = false;
			}
		}
		return false;
	}

	public boolean hasWay(int s, int e) {
		Stack<Integer> stack = new Stack<>();
		int v = s;
		boolean cont = true;
		int m[][] = matrix;
		a: while (cont) {
			for (int i = 0; i < this.size(); i++) {
				if (m[v][i] == 1) {
					if (i == e)
						return true;
					else {
						stack.push(v);
						m[v][i] = 0;
						v = i;
						continue a;
					}
				}
			}
			if (stack.size() != 0) {
				v = stack.pop();

				continue a;
			} else {
				cont = false;
			}
		}
		return false;
	}

	public int[][] copyMatrix() {
		int[][] result = new int[size()][size()];
		for (int i = 0; i < size(); i++) {
			for (int j = 0; j < size(); j++) {
				result[i][j] = matrix[i][j];
			}
		}
		return result;
	}

	public int numberWay(int s, int e) {
		Stack<Integer> stack = new Stack<>();
		int v = s;
		boolean cont = true;

		int m[][] = copyMatrix();
		System.out.println("1 : " + toString());
		int count = 0;
		if (s == e) {
			m = null;
			return count;
		}
		a: while (cont) {
			for (int i = 0; i < this.size(); i++) {
				if (m[v][i] == 1) {
					count++;
					System.out.println("m[" + v + "][" + i + "]=" + count
							+ "; e = " + e);
					if (i == e) {
						m = null;
						return count;
					} else {
						System.out.println("2 : " + toString());
						stack.push(v);
						m[v][i] = 0;
						m[i][v] = 0;
						v = i;
						continue a;
					}
				}
			}
			if (stack.size() != 0) {
				System.out.println("3 : " + toString());
				v = stack.pop();
				count--;
				continue a;
			} else {
				count = -1;
				cont = false;
			}
		}
		m = null;
		return count;
	}

	@Override
	public boolean isEuler() {
		if (!isConnection())
			return false;
		else
			for (int i = 0; i < size(); i++) {
				if (deg(i) % 2 != 0)
					return false;

			}

		return true;
	}

	public String printMang(int a[][]) {
		String result = "";
		for (int[] is : a) {
			for (int i : is) {
				result = result + " " + i;
			}
			result = result + "\n";
		}
		return result;
	}

	public boolean isExitEdge(int a[][]) {
		String result = "";
		for (int[] is : a) {
			for (int i : is) {
				if (i == 1)
					return false;
			}
		}
		return true;
	}

	@Override
	public String findEuler() {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (isEuler()) {
			List<Integer> circle = new ArrayList<Integer>();
			IGraph temp = this;
			int v = 0;
			circle.add(v);
			a: for (int i = 0; i < size(); i = v) {
				for (int j = 0; j < size(); j++) {
					if (temp.matrix[i][j] == 1) {
						v = j;
						circle.add(j);
						temp.removeEdge(i, j);

						if (circle.get(0) == circle.get(circle.size() - 1)
								&& circle.size() > 1) {
							list.add(circle);
							if (list.size() == 2) {
								List<Integer> join = join(list.get(0),
										list.get(1));
								list = new ArrayList<List<Integer>>();
								list.add(join);
							}
							if (temp.numberSumEdge() == 0) {
								break a;
							}
							for (int j2 = 0; j2 < circle.size(); j2++) {
								if (temp.deg(circle.get(j2)) > 0) {
									v = circle.get(j2);
									circle = new ArrayList<Integer>();
									circle.add(v);
									continue a;
								}
							}

						}
						break;
					}
				}
			}
			String result = "";
			if (list.size() == 1) {
				List<Integer> c = list.get(0);
				for (int i = 0; i < c.size(); i++) {
					result = result + c.get(i) + " ";
				}
			}
			return result;
		} else
			return null;
	}

	public List<Integer> join(List<Integer> cicle1, List<Integer> cicle2) {
		List<Integer> result = new ArrayList<Integer>();
		for (int i = 0; i < cicle1.size(); i++) {
			if (cicle1.get(i) == cicle2.get(0)) {
				result.addAll(cicle2);
			} else {
				result.add(cicle1.get(i));
			}

		}
		return result;
	}

	@Override
	public void removeEdge(int col, int row) {
		matrix[row][col] = 0;
		matrix[col][row] = 0;

	}

	@Override
	public boolean hasWayEuler() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public String findWayEuler() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isTree() {
		if (size() == numberSumEdge() + 1) {
			return true;
		}
		return false;
	}

	@Override
	public List<Integer> mathEccentricity() {
		if (isTree()) {
			FreeTree temp = new FreeTree(matrix, numberPoints);
			return temp.mathEccentricity();
		}
		return null;

	}

	public FreeTree prim() {
		List<Integer> listV = new ArrayList<>();
		int v = 0;
		listV.add(v);
		double min = Double.POSITIVE_INFINITY;
		int point = -1;
		int point_pre = -1;
		MatrixWeight matrixResult = new MatrixWeight(size());
		double[][] temp = Util.getUtil().copyMatrix(matrixWeight.getMatrix());
		while (listV.size() < size()) {
			for (int i = 0; i < listV.size(); i++) {
				for (int j = 0; j < size(); j++) {
					if (temp[listV.get(i)][j] < min) {
						min = temp[listV.get(i)][j];
						point_pre = listV.get(i);
						point = j;
					}
				}
			}
			System.out.println("Min :" + point_pre + "," + point + "," + min);
			// System.out.println(point_pre + " : " + point);
			if (!listV.contains(point)) {
				matrixResult.add(point_pre, point, min);
				listV.add(point);
			}
			temp[point_pre][point] = Double.POSITIVE_INFINITY;
			temp[point][point_pre] = Double.POSITIVE_INFINITY;
			min = Double.POSITIVE_INFINITY;
			System.out.println(matrixResult.toString());
		}
		List<Point> points = new ArrayList<>();
		for (int i = 0; i < size(); i++) {
			points.add(numberPoints.get(listV.get(i)));
		}
		return new FreeTree(matrixWeight, numberPoints);

	}
}
